Busqueda entre adversarios

Juegos

Los juegos han ocupado las facultades intelectuales de la gente (a veces a un grado alarmante) mientras ha existido la civilizacion. Para los investigadores de IA, la naturaleza abstracta de los juegos los hacen un tema atractivo a estudiar. El estado de un juego es facil de representar, y los agentes estan restringidos, por lo general, a un pequeno numero de acciones cuyos resultados estan definidos por reglas precisas. Los juegos fisicos, como croquet y hockey sobre hielo, tienen descripciones mucho mas complicadas, una variedad mucho mas grande de acciones posibles, y reglas bastante imprecisas que definen la legalidad de las acciones. A excepcion del futbol de robots, estos juegos fisicos no han tenido mucho interes en la comunidad de IA. El jugar a juegos fue una de las primeras tareas emprendidas en IA. Hacia 1950, casi tan pronto como los computadores se hicieron programables, el ajedrez fue abordado por Konrad Zuse (el inventor del primer computador programable y del primer lenguaje de programacion), por Claude Shannon (el inventor de la teoria de informacion), por Norbert Wiener (el creador de la teoria de control moderna), y por Alan Turing. Desde entonces, hubo un progreso continuo en el nivel de juego, hasta tal punto que las maquinas han superado a la gente en las damas y en Otelo, han derrotado a campeones humanos (aunque no siempre) en ajedrez y backgammon, y son competitivos en muchos otros juegos. La excepcion principal es Go, en el que los computadores funcionan a nivel aficionado.

Decisiones optimas en juegos

Consideraremos juegos con dos jugadores, que llamaremos MAX y MIN por motivos que pronto se haran evidentes. MAX mueve primero, y luego mueven por turno hasta que el juego se termina. Al final de juego, se conceden puntos al jugador ganador y penalizaciones al perdedor. Un juego puede definirse formalmente como una clase de problemas de busqueda con los componentes siguientes: • El estado inicial, que incluye la posicion del tablero e identifica al jugador que mueve. • Una funcion sucesor, que devuelve una lista de pares (movimiento, estado), indicando un movimiento legal y el estado que resulta. • Un test terminal, que determina cuando se termina el juego. A los estados donde el juego se ha terminado se les llaman estados terminales. • Una funcion utilidad (tambien llamada funcion objetivo o funcion de rentabilidad), que da un valor numerico a los estados terminales. En el ajedrez, el resultado es un triunfo, perdida, o empate, con valores 1, 1 o 0. Algunos juegos tienen una variedad mas amplia de resultados posibles: las rentabilidades en el backgammon se extienden desde 192 a 192. Este capitulo trata principalmente juegos de suma cero, aunque mencionemos brevemente juegos con «suma no cero».

Poda alfa-beta

El problema de la busqueda minimax es que el numero de estados que tiene que examinar es exponencial en el numero de movimientos. Lamentablemente no podemos eliminar el exponente, pero podemos dividirlo, con eficacia, en la mitad. La jugada es que es posible calcular la decision minimax correcta sin mirar todos los nodos en el arbol de juegos.

Decisiones en tiempo real imperfectas

El algoritmo minimax genera el espacio de busqueda entero, mientras que el algoritmo alfa-beta permite que podemos partes grandes de el. Sin embargo, alfa-beta todavia tiene que buscar en todos los caminos, hasta los estados terminales, para una parte del espacio de busqueda. Esta profundidad no es, por lo general, practica porque los movimientos deben hacerse en una cantidad razonable de tiempo (tipicamente, unos minutos como maximo). El trabajo de Shannon en 1950, Programming a computer for playing chess, propuso un cambio: que los programas deberian cortar la busqueda antes y entonces aplicar una funcion de evaluacion heuristica a los estados, convirtiendo, efectivamente, los nodos no terminales en hojas terminales. En otras palabras, la sugerencia debera alterar minimax o alfa-beta de dos formas: se sustituye la funcion de utilidad por una funcion de evaluacion heuristica EVAL, que da una estimacion de la utilidad de la posicion, y se sustituye el test-terminal por un test-limite que decide cuando aplicar EVAL

Juegos que incluyen un elemento de posibilidad

En la vida real, hay muchos acontecimientos imprevisibles externos que nos ponen en situaciones inesperadas. Muchos juegos reflejan esta imprevisibilidad con la inclusion de un elemento aleatorio, como el lanzamiento de dados. De esta manera, ellos nos dan un paso mas cercano a la realidad, y vale la pena ver como afecta al proceso de toma de decisiones. Backgammon es un juego tipico que combina la suerte y la habilidad. Se hacen rodar unos dados, al comienzo del turno de un jugador, para determinar los movimientos legales. En la posicion backgammon de la Figura 6.10, por ejemplo, Blanco ha hecho rodar un 6-5, y tiene cuatro movimientos posibles. Aunque Blanco sabe cuales son sus propios movimientos legales, no sabe lo que le va a salir a Negro con los dados y por eso no sabe cuales seran sus movimientos legales. Esto significa que Blanco no puede construir un arbol de juegos estandar de la forma que vimos en el ajedrez y tic-tac-toe. Un arbol de juegos en el backgammon debe incluir nodos de posibilidad ademas de los nodos MAX y MIN. En la Figura 6.11 se rodean con circulos los nodos de posibilidad. Las ramas que salen desde cada nodo posibilidad denotan las posibles tiradas, y cada una se etiqueta con la tirada y la posibilidad de que ocurra. Hay 36 resultados al hacer rodar dos dados, cada uno igualmente probable; pero como un 6-5 es lo mismo que un 5-6, hay solo 21 resultado distintos. Los seis dobles (1-1 a 6-6) tienen una posibilidad de 1/36, los otros 15 resultados distintos un 1/18 cada uno.

Programas de juegos

Podriamos decir que jugar a juegos es a IA como el Gran Premio de carreras de automoviles es a la industria de coches: los programas de juegos son deslumbrantemente rapidos, maquinas increiblemente bien ajustadas que incorporan tecnicas muy avanzadas de la ingenieria, pero no son de mucho uso para hacer la compra. Aunque algunos investigadores crean que jugar a juegos es algo irrelevante en la corriente principal de IA, se sigue generando entusiasmo y una corriente estable de innovaciones que se han adoptado por la comunidad. Ajedrez: en 1957, Herbert Simon predijo que dentro de 10 anos los computadores ganarian al campeon mundial humano. Cuarenta anos mas tarde, el programa Deep Blue derroto a Garry Kasparov en un partido de exhibicion a seis juegos. Simon se equivoco, pero solo por un factor de 4. Kasparov escribio: El juego decisivo del partido fue el juego 2, que dejo una huella en mi memoria... Vimos algo que fue mas alla de nuestras expectativas mas salvajes de como un computador seria capaz de prever las consecuencias posicionales a largo plazo de sus decisiones. La maquina rechazo moverse a una posicion que tenia una ventaja decisiva a corto plazo, mostrando un sentido muy humano del peligro. (Kasparov, 1997) Deep Blue fue desarrollado por Murray Campbell, Feng-Hsiung Hsu, y Joseph Hoane en IBM (vease Campbell et al., 2002), construido sobre el diseno de Deep Thought desarrollado anteriomente por Campbell y Hsu en Carnegie Mellon. La maquina ganadora era un computador paralelo con 30 procesadores IBM RS/6000 que controlaba la «busqueda software» y 480 procesadores VLSI, encargados para el ajedrez, que realizaron la generacion de movimientos (incluso el movimiento de ordenacion), la «busqueda hardware» para los ultimos niveles del arbol, y la evaluacion de los nodos hoja. Deep Blue busco 126 millones de nodos por segundo, como regla general, con una velocidad maxima de 330 millones de nodos por segundo. Genero hasta 30 billones de posiciones por movimiento, y alcanzo la profundidad 14 rutinariamente. El corazon de la maquina es una busqueda alfa-beta estandar de profundidad iterativa con una tabla de transposiciones, pero la llave de su exito parece haber estado en su capacidad de generar extensiones mas alla del limite de profundidad para lineas suficientemente interesantes.

Discusiones

Como el calculo de decisiones optimas en juegos es intratable en la mayoria de los casos, todos los algoritmos deben hacer algunas suposiciones y aproximaciones. La aproximacion estandar, basada en minimax, funciones de evaluacion y alfa-beta, es solamente un modo de hacerlo. Probablemente porque la propusieron tan pronto, la aproximacion estandar fue desarrollada intensivamente y domina otros metodos en los juegos de turnos. Algunos en el campo creen que esto ha causado que jugar a juegos llegue a divorciarse de la corriente principal de investigacion de IA, porque la aproximacion estandar no proporciona mucho mas espacio para nuevas perspicacias en cuestiones generales de la toma de decisiones. En esta seccion, vemos las alternativas.

hecho por Jorge Daniel